package main.leetcode.clockin.June;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 990. 等式方程的可满足性
 *
 * <p>给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b
 * 是小写字母（不一定不同），表示单字母变量名。
 *
 * <p>只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
 *
 * <p>示例 1：输入：["a==b","b!=a"] 输出：false 解释：如果我们指定，a = 1 且 b = 1，
 * 那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
 *
 * <p>示例 2：输出：["b==a","a==b"] 输入：true 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
 *
 * <p>示例 3：输入：["a==b","b==c","a==c"] 输出：true
 *
 * <p>示例 4：输入：["a==b","b!=c","c==a"] 输出：false
 *
 * <p>示例 5：输入：["c==c","b==d","x!=z"] 输出：true
 *
 * <p>提示：<br>
 * 1 <= equations.length <= 500 <br>
 * equations[i].length == 4 <br>
 * equations[i][0] 和 equations[i][3] 是小写字母 <br>
 * equations[i][1] 要么是 '='，要么是 '!' <br>
 * equations[i][2] 是 '='
 */
public class day8 {
    public static void main(String[] args) {
        System.out.println(
                new Solution2().equationsPossible(new String[] {"a==b", "c==d", "a==c", "a!=d"}));
        System.out.println(
                new Solution2()
                        .equationsPossible(
                                new String[] {
                                    "f==g", "d!=a", "d==f", "i!=i", "j==a", "g==i", "h!=h", "k==f",
                                    "d==g", "k==k"
                                }));
        System.out.println(
                new Solution2().equationsPossible(new String[] {"c==c", "b==d", "x!=z"}));
        System.out.println(new Solution2().equationsPossible(new String[] {"a!=a"}));
        System.out.println(
                new Solution2().equationsPossible(new String[] {"a==b", "b!=c", "c==a"}));
        System.out.println(new Solution2().equationsPossible(new String[] {"a==b", "b!=a"}));
        System.out.println(new Solution2().equationsPossible(new String[] {"b==a", "a==b"}));
        System.out.println(
                new Solution2().equationsPossible(new String[] {"a==b", "b==c", "a==c"}));
        System.out.println(
                new Solution2().equationsPossible(new String[] {"a==b", "e==c", "b==c", "a!=e"}));
    }

    /** 超高校级的低配并查集（bushi， 因为没有并查集的经验所以全程采用map进行递归查找 */
    static class Solution1 {
        public boolean equationsPossible(String[] equations) {
            HashMap<Character, HashSet<Character>> map = new HashMap<>();
            char left, right;
            // 记录相同集
            for (String equation : equations) {
                char[] chars = equation.toCharArray();
                if (chars[1] == '=') {
                    left = chars[0];
                    right = chars[3];
                    addEqualToMap(left, right, map);
                    addEqualToMap(right, left, map);
                }
            }

            // 记录已经访问过的状态防止死循环
            boolean[] isVisited = new boolean[26];
            for (String equation : equations) {
                char[] chars = equation.toCharArray();
                if (chars[1] == '!') {
                    left = chars[0];
                    right = chars[3];
                    // 遍历相等集，如果两者相等，则不满足
                    if (left == right || isEqual(isVisited, left, right, map)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean isEqual(
                boolean[] isVisited,
                char left,
                char right,
                HashMap<Character, HashSet<Character>> map) {
            HashSet<Character> set = map.get(left);
            if (set == null) {
                return false;
            }
            if (set.contains(right)) {
                return true;
            }
            // 记录状态
            isVisited[left - 'a'] = true;
            for (Character character : set) {
                if (isVisited[character - 'a']) {
                    continue;
                }
                if (isEqual(isVisited, character, right, map)) {
                    return true;
                }
            }
            // 状态还原
            isVisited[left - 'a'] = false;
            return false;
        }

        private void addEqualToMap(
                char left, char right, HashMap<Character, HashSet<Character>> map) {
            map.computeIfAbsent(left, character -> new HashSet<>());
            map.get(left).add(right);
        }
    }

    /** 并查集 */
    static class Solution2 {
        public boolean equationsPossible(String[] equations) {
            // 记录父节点，没有相等项的父节点就是自身
            int[] parent = new int[26];
            for (int i = 0; i < 26; ++i) {
                parent[i] = i;
            }
            int left, right;
            // 记录相同集
            for (String equation : equations) {
                char[] chars = equation.toCharArray();
                if (chars[1] == '=') {
                    left = chars[0] - 'a';
                    right = chars[3] - 'a';
                    union(parent, left, right);
                }
            }

            for (String equation : equations) {
                char[] chars = equation.toCharArray();
                if (chars[1] == '!') {
                    left = chars[0] - 'a';
                    right = chars[3] - 'a';
                    // 根节点相同
                    if (find(parent, left) == find(parent, right)) {
                        return false;
                    }
                }
            }
            return true;
        }

        /**
         * 合并
         *
         * @param parent 根数组
         * @param left 相等项1
         * @param right 相等项2
         */
        private void union(int[] parent, int left, int right) {
            parent[find(parent, left)] = find(parent, right);
        }

        /**
         * 路径压缩，并返回根节点
         *
         * @param parent 父节点数组
         * @param index 当前节点
         * @return 根节点下标
         */
        private int find(int[] parent, int index) {
            while (parent[index] != index) {
                parent[index] = parent[parent[index]];
                index = parent[index];
            }
            return index;
        }
    }
}
